A self-organizing list is a list that reorders its items based on some self-organizing heuristic. A self-organizing list has many applications in computer science. One application is to reduce the average search time of a linear search by moving frequently accessed items nearer to the front of the list. Compilers may use self-organizing lists for their symbol tables. Caching algorithms may use self-organizing lists to determine which items to replace when a central processing unit (CPU) accesses a memory location that is not currently resident in a cache. Another application is to compress data. If input data contains symbols with a high local correlation of frequencies, then the entropy of a message can be reduced by transmitting an index value of the list item containing the symbol rather than the symbol itself. By doing this, and then reorganizing the list according to a self-organizing heuristic, the index values output from the list will tend to be low in numerical value. This enables a subsequent stage such as an entropy encoder (e.g., a Huffman encoder or a range coder) to achieve higher compression results.
There are many self-organizing heuristics in use. Some of the more popular ones include:                Move-To-Front (MTF): When an item is accessed, that item is moved to the front of the list. The list is rearranged such that all other items remain in the same relative order.        Move-One-From-Front (M1FF)—When an item is accessed, it is moved one position from the front of the list unless it is the second item in the list. In that case, it is moved to the front.        Transpose: When an item is accessed, that item is swapped with the item one position closer to the front of the list.        Best x of 2x−1: Given any two symbols in the list, the symbol that was requested “x” or more times in the previous “2x−1” requests for either symbol is in front. Move-To-Front can be described as “Best 1 of 1”.        Timestamp: This is “Best 2 of 3” which is a specific form of “Best x of 2x−1”.        
The performance of accessing and maintaining a self-organizing list varies widely. The best case access time is “1” when the item being accessed is at the front of the list. The worst case access time is “n”, where n is the number of items in the list. The average case access time can be shown to be:Tavg=1*p(1)+2*p(2)+3*p(3)+4*p(4) . . . +n*p(n)
where p(i) is the probability of accessing the ith element in the list.
The performance of a self-organizing list is data-dependent and unpredictable. Known techniques attempt to reduce the average case access time. An example technique is to initialize the list in the order of diminishing probabilities. However, a drawback in this known technique is that in many cases the probabilities are unknown at initialization. Accordingly, it is not possible to determine the optimal initialization sequence. Another drawback with this initialization technique as well as other known techniques is that all of the techniques have the same worst case access time.